A distributed database is a database in which the data is not stored at a single physical location. Instead, it is spread across a network of database nodes that are geographically dispersed and connected via communications links. FIG. 1 illustrates schematically an example of a distributed database system providing data access to a database client. The distributed database is comprised of a number of database (DB) nodes, with each database node being comprised of an interface, distribution logic, a storage unit, and a network connection. The interface (e.g. a northbound interface) receives requests from one or more apparatuses, referred to as “clients” of the distributed database, that use the data held by the database to execute one or more applications. Such an interface typically makes use of a data access protocol, such as the Lightweight Directory Access Protocol (LDAP). The requests received from the database client are commonly referred to as “data queries”. For example, a database node may receive a query that requires retrieval (i.e. reading) of an item of data that is already stored by the distributed database (e.g. location information relating to a particular user of a telecommunications system). Alternatively, a database node may receive a query that requires storage (i.e. writing) of a new item of data into the database, as this data has not previously been stored by the distributed database. As a further example, a database node may receive a query that requires that an item of data that is already stored by the distributed database is overwritten by or updated with new data (e.g. storing updated location information of a user).
The distribution logic provides access to the data distributed among the plurality of database nodes that make up the distributed database. Typically, the distribution logic will function in a transparent manner such that a client perceives the distributed database to be a single logical database. A database client therefore does not need to know where any particular item of data is stored, since the distribution logic of the distributed database enables this complexity to be hidden from the client. Accordingly, a database client is usually configured to route any data queries towards one of the database nodes that acts as a so-called ‘single point of access’ for that client. A database client could also be configured to contact an alternative, back-up database node, should any attempt to contact the first database node fail. In FIG. 1, each of the database nodes are illustrated as including their own distribution logic unit. For example, this distribution logic unit could comprise a simple data table stored therein that enables the database node to determine which database node stores (or is intended to store) a specific item of data. However, this distribution logic can also be implemented in other ways. For example, as an alternative, the distribution logic could be implemented in a central node, such that each database node will be required to contact the central node in order to locate a specific item of data.
A database node that receives a request or query uses the distribution logic to determine whether or not it stores the data or, if the query requires that some data be written into the database, whether or not it is intended to store the data. If it does not store or is not intended to store the data, the distribution logic will then determine which of the other database nodes it should forward the query to. For example, the distribution logic may be able to determine exactly which of the other database nodes stores or should store the data that is the subject of the query, and will therefore ensure that the query is forwarded towards this database node. Alternatively, the distribution logic may not be able to determine exactly which of the other database nodes stores or should store the data, but may merely be able to determine which other database node it can forward the received query to in order to ensure that the query is routed towards the database node that stores or should store the data. For example, the distribution logic may be able to identify one of the other database nodes that is ‘closer’ to the database node which stores or should store that data. If a data request relates to an entirely new item of data that has not previously been stored in the database, then the distribution logic can use one of a number of different methods to determine which of the database nodes should store this data. For example, a hash of the data can be calculated and used as an index for identifying the database node that stores or is intended to store the data. Alternatively, the database node that is to store this new data can be selected according to the available storage capacity of each of the database nodes, the geographical position of each of the database nodes with respect to the client that generating the request etc.
The storage unit (or memory) stores the data that is the responsibility of that particular database node. The portion of the data that is stored at an individual database node is referred to as the database nodes data set (DS). For example, in FIG. 1 DB Node 1 stores DS1, DB Node 2 stores DS2, DB Node 3 stores DS3, and DB Node 4 stores DS4. It is common for a distributed database solution to divide the data to be stored into a number of “partitions”, with the data falling within a particular partition being assigned to a data set stored at a particular database node. For example, a partition may comprise user data relating to a certain range of user identifiers, such as ranges of MSISDN numbers. In addition, some or all of the partitions can be replicated in one or more database nodes for security and/or availability purposes. For example, the data stored by DB Node 3 (DS3) can comprise, among other data, user data from within a first data partition that comprises MSISDN numbers from 2000000 to 3999999. The data stored by DB Node 4 (DS4) can comprise, among other data, user data from within a second data partition that comprises MSISDN numbers from 4000000 to 5999999. However, DS3 can further comprise a replicated copy of some or all of the data stored as a master copy by DB node 4 (i.e. DS4).
A database client can be, for example, an application server, a user terminal, or any other kind of apparatus that implements applications that are arranged to send requests/queries to the database to obtain and/or manipulate data. Generally, the database clients will implement applications that use the data stored by the distributed database to provide some specific services. For example, a first database client can implement a HLR or HSS application for providing 2G or 3G home registration services for users subscribed to a certain mobile telecom operator, whilst a second database client can implement an application that provides positioning-based services for some of these users. Accordingly, both of these applications may need to access data relating to the same users, which can be stored at one or more of the database nodes of a distributed database.
As the entirety of the data stored by a distributed database is distributed across the system, not all of the data is held by every database node, even if a degree of replication is implemented. As such, this will often mean that a data request that is sent to a first database node will relate to data that is not stored or is not intended to be stored at that database node. The data request must therefore be forwarded to a second database node within the distributed database system that holds either the master copy or a replicated copy of that data. The database node that first receives a request from a database client (i.e. as the client's point of access to the database) is referred to as the local database node, whilst the other database nodes within the distributed database are referred to as remote database nodes. Depending on where (i.e. at which remote database node) the data is stored or is intended to be stored, the time taken to handle the data request can vary, due mainly to the inherent transmission delays of the network that increase as the distance between the database nodes increases. Such access latency is typically around 1 ms per 100 km, but can change substantially subject to network conditions and/or network reconfigurations.
FIG. 2 is an example signalling flow diagram of a database client accessing data stored in a remote database node of a distributed database. The steps performed are as follows:                A1. A client sends a request relating to some data to the distributed database. To do so, the client is configured with the identity/address of one of the plurality of database nodes that is to act as a point of contact for the client. In this example, the client sends the query to its local database node, DB Node 1.        A2. The distribution logic of DB Node 1 processes the request to determine whether or not it stores or is intended to store that data to which the request relates. In this example, DB Node 1 determines that the request relates to data that is stored or is intended to be stored at a remote database node, DB Node 2, and forwards the request on to the DB Node 2.        A3. The distribution logic of DB Node 2 processes the request, determines that the data is stored or is intended to be stored in the storage unit of DB Node 2. DB Node 2 therefore attempts to complete the requested action, generates a response to the data request, and sends the response back to DB Node 1.        A4. DB Node 1 receives the response from DB Node 2, and forwards the response on to the client.        
The delay/latency experienced by the client prior to receiving the response to the request will depend upon the distance between the database nodes, the internal processing time of each of the database nodes, the network bandwidth and any other limitations of the connections between the database nodes.
The additional latency introduced through the use of a distributed database is undesirable. In particular, the latency requirements, with regard to the time that elapses between the sending of a query from a database client and the reception by the client of the corresponding reply, can vary substantially from one application to another. For example, the latency requirements of a database client that provides a HLR or HSS application can be stricter (e.g. require shorter response times) than those required by database clients that provide positioning-based services. It is therefore preferable that a distributed database be arranged such that it can meet the latency requirements of all of the applications that it is required to serve.
One approach that attempts to ensure that a distributed database can meet all latency requirements can comprise distributing the data among the nodes of the database according to the latencies required by each database client/application, and configuring each database client/application to communicate with certain database nodes accordingly. However, maintaining this configuration can be extremely difficult when more database nodes are added to the distributed database, when a database node is replaced by a new one with different performance characteristics, and/or when new database clients/applications are deployed. Furthermore, the performance of any of the plurality of database nodes can change over time.
An alternative approach can be envisaged in which items of data stored within the distributed database are moved to the database node that last received a request relating to that data. For example, following initial configuration DB Node 1 may store a particular item of data. When DB Node 2 then receives a request relating to this data, such that the request has to be forwarded to DB Node 1 in order to be completed, the data is moved to DB Node 2. Whilst such an approach may temporarily minimise the latency for requests relating to this data that are subsequently sent to the same database node, by providing that this data is now stored “locally”, they do not solve the problem of how to ensure that the database can meet the latency requirements of all applications, as these applications can be implemented at database clients that are not served by this database node. For example, an application at another database client may send a request relating to this data to DB Node 3, which will then result in the data being moved from DB Node 2 to DB Node 3. A subsequent data request relating to this data that is sent to DB Node 2 will then result in the data being moved back from DB Node 3 to DB Node 2. This could result in continuous or near-continuous redistribution of data between the database nodes, generating large amounts of traffic between the database nodes and only occasionally meeting the latency requirements of the applications implemented at database clients.